CSP2019 题解

快要 csp2020 了，来补 2019 的题（咕

D1T1

手玩就出来了？

D1T2

容易想到统计每个节点为右端点的子串数，然后继承给子节点就好了。然后记录每个节点祖先中离它最近的未匹配的 ‘(‘ 是哪个，再记录一下每个节点为右端点的合法的 ‘(…)’ 数，就好了！

条条大路通罗马，有时候错误的思路也会导出正确的思路。要有信仰！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 5e5 + 10;
ll n, res;
ll fa[N], ans[N], lst[N], cur[N];
char s[N];

int main() {
    cin >> n;
    scanf("%s", s + 1);
    rep(i, 2, n) scanf("%lld", &fa[i]);
    rep(x, 1, n) {
        ans[x] = ans[fa[x]];
        lst[x] = lst[fa[x]];
        if (s[x] == '(') lst[x] = x;
        else if (s[x] == ')' && lst[x]) {
            cur[x] = cur[fa[lst[x]]] + 1;
            lst[x] = lst[fa[lst[x]]];
            ans[x] += cur[x];
        }
        res ^= (1ll * x * ans[x]);
    }
    printf("%lld\n", res);
    return 0;
}

D1T3

部分分推出正解。

菊花：将数字按照 $(rt, p_1, p_2, … p_{n - 1})$ 排出来，发现相当于每个位置上的数往后移了一位。贪心的构造轮换。

链：对于在 $u$ 位置的要移到 $v$ 位置（假设 $u < v$），显然 $[u, v]$ 之间的删边顺序是从左到右，$u$ 右边比 $u$ 左边删的早。打标记，$i$ 点 $tag_i = 0, 1, 2$ 表示无标记，先左后右，先右后左

这是很有启发性的两档分！接下来考虑满分做法，显然就是 $u$ 指向 $v$ 的出边是第一个删的，$v$ 指向 $u$ 的出边是第一个删的，$[u, v]$ 之间的点都还没被删。
抽象一点就是把图分成很多不相交的链了。

复杂度 $O(n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int mod = 1e9 + 7, N = 2e3 + 10;
int T, n, w[N];
int to[N << 1], nxt[N << 1], lnk[N], cnt;
struct node {
    int deg, beg, end, fa[N];  // end 和 beg 分别记录该点第一条删除的入边和出边，fa 将成对删除的邻边绑在一起
    bool st[N], ed[N];  // ed 和 st 是记录某条边有无作为该边的 入/出 边，至于为什么要分开记录还不是很懂。。
    void init() {
        beg = end = -1, deg = 0;
        rep(i, 0, n) st[i] = ed[i] = 1, fa[i] = i;
    }
    int getfa(int x) { return fa[x] == x ? x : fa[x] = getfa(fa[x]); }
}a[N];

void add(int x, int y) {
    to[cnt] = y, nxt[cnt] = lnk[x], lnk[x] = cnt, ++cnt;
}

int getpos(int x, int id) {
    int ret = n + 1;
    if (~id && (a[x].end == -1 || a[x].end == id)) {
        if (a[x].ed[id] && (a[x].beg == -1 || a[x].deg <= 1 || a[x].getfa(id) != a[x].getfa(a[x].beg)))
            ret = x;
    }
    for (int i = lnk[x]; ~i; i = nxt[i]) {
        if (id == (i >> 1)) continue;
        int ed = (i >> 1), y = to[i];
        if (~id) {
            if (id == a[x].end || ed == a[x].beg || a[x].getfa(id) == a[x].getfa(ed))
                continue;
            if (!a[x].ed[id] || !a[x].st[ed]) continue;
            if (~a[x].beg && ~a[x].end && a[x].deg > 2 && a[x].getfa(id) == a[x].getfa(a[x].beg) && a[x].getfa(ed) == a[x].getfa(a[x].end))
                continue;
            ret = min(ret, getpos(y, ed));
        } else {
            if (a[x].beg == -1 || a[x].beg == ed) {
                if (!a[x].st[ed]) continue;
                if (~a[x].end && a[x].deg > 1 && a[x].getfa(ed) == a[x].getfa(a[x].end)) continue;
                ret = min(ret, getpos(y, ed));
            }
        }
    }
    return ret;
}

bool Link(int x, int id, int p) {
    if (x == p) return a[x].end = id, 1;
    for (int i = lnk[x]; ~i; i = nxt[i]) {
        if (id == (i >> 1)) continue;
        int ed = (i >> 1), y = to[i];
        if (Link(y, ed, p)) {
            if (~id) {
                a[x].ed[id] = a[x].st[ed] = 0, --a[x].deg;
                a[x].fa[a[x].getfa(id)] = a[x].getfa(ed);
            } else {
                a[x].beg = ed;
            } return 1;
        }
    } return 0;
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        memset(lnk, -1, sizeof(lnk));
        cnt = 0;
        rep(i, 1, n) {
            scanf("%d", &w[i]);
            a[i].init();
        }
        rep(i, 1, n - 1) {
            int x, y; scanf("%d%d", &x, &y);
            add(x, y), add(y, x);
            ++a[x].deg, ++a[y].deg;
        }
        rep(i, 1, n) {
            int pos = getpos(w[i], -1);
            Link(w[i], -1, pos);
            printf("%d ", pos);
        } puts("");
    }
    return 0;
}

D2T1

（啊。。这个题目真的恶心。。差点没懂）

考虑每种食材都不超过 $\lfloor \frac{k}{2} \rfloor$ 这个限制很烦，考虑容斥，统计每种食材打破限制的总方案数然后减掉就好了。

对于第 $col$ 种食材打破限制，设 $f[i, j]$ 表示前 $i$ 个烹饪方法中选的第 $col$ 种食材的菜与不是第 $col$ 种食材的菜的个数差为 $j$ 的方案数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int mod = 998244353, N = 102, M = 2002;
typedef long long ll;
ll n, m, tot = 1, ans;
ll a[N][M], f[N][N << 1], s[N];

int main() {
    cin >> n >> m;
    rep(i, 1, n) {
        rep(j, 1, m)
            scanf("%lld", &a[i][j]), s[i] = (s[i] + a[i][j]) % mod;
        tot = tot * (s[i] + 1) % mod;
    }
    rep(col, 1, m) {
        f[0][N] = 1;
        rep(i, 1, n)
            rep(j, N - i, N + i)
                f[i][j] = (f[i - 1][j] + f[i - 1][j - 1] * a[i][col] % mod + f[i - 1][j + 1] * (s[i] - a[i][col] + mod) % mod) % mod;
        rep(i, 1, n) ans = (ans + f[n][N + i]) % mod;
    }
    printf("%lld\n", (tot - 1 - ans + mod) % mod);
    return 0;
}

D2T2

考场上写了 $n^3$ 暴力后突然聪明了一下，输出了一些东西，发现这玩意是单调的然后就多了 32 分 qvq 论信仰的力量。。

88 分就是再加个单调队列！100 分再加个高精度。。。

具体来说，$j$ 能转移到 i 当且仅当 $pre[i] - pre[j] >= len[j]$，$len[j]$ 表示以 $j$ 为结束的段，$pre[i] >= pre[j] + len[j]$。发现 $j$ 越大越好（这就是我考场上发现的单调性），单调队列一波就可以了。

单调性的证明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 88 分代码
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

typedef long long ll;
const int N = 4e7 + 5;
ll n, tp, len[N], f[N], q[N], pre[N];

int main() {
    cin >> n >> tp;
    rep(i, 1, n) {
        scanf("%lld", &pre[i]);
        pre[i] += pre[i - 1];
    }
    int l = 1, r = 0;
    q[++r] = 0;
    rep(i, 1, n) {
        while (l < r && pre[q[l + 1]] + len[q[l + 1]] <= pre[i]) ++l;
        len[i] = pre[i] - pre[q[l]];
        f[i] = f[q[l]] + (pre[i] - pre[q[l]]) * (pre[i] - pre[q[l]]);
        while (l <= r && pre[q[r]] + len[q[r]] >= pre[i] + len[i]) --r;
        q[++r] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

D2T3

学习了 xht37 的思路（是我比较适应的方法）：算出每一个节点为重心的次数。

选一个重心为根，对于我们考虑的 $x (x\neq rt)$，割的边一定不在 x 的子树里。设 $mx[x] = \max\{size[y]\}$, $S$ = 割掉边后不包含 $x$ 的那块的 $size$，那么有：$2(n - S - size[x]) \leq n - S$, $2mx[x] \leq n - S$，也就是要求 $n - 2size[x] \leq S \leq n - 2mx[x]$ 且边不在 $x$ 子树中的边数

那个不等式用树状数组维护一下，就成了区间求和；第二个约束可以在进出某个子树的时候作差。

$x = rt$ 时怎么办？设 $size$ 最大的子树是 $u$ 的，次大的是 $v$ 的。割边在 $u$ 子树中时 $2size[u] \leq n - S$, 在 $v$ 子树中时 $2size[v] \leq n - S$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 3e5 + 10;
typedef long long ll;
int T, n, rt, u, v;
int sz[N], mx[N], C1[N], C2[N];
ll ans;
bool mark[N];
vector<int> g[N];

void add(int C[], int x, int v) {
    ++x;  // 使得 x 不为 0 的技巧
    for (; x <= n + 1; x += lowbit(x)) C[x] += v;  // !!!
}

int ask(int C[], int x) {
    ++x;  // 查询也一定要啊！！！
    int ret = 0;
    for (; x; x -= lowbit(x)) ret += C[x];
    return ret;
}

void dfs1(int x, int fa) {
    bool ff = 1;
    sz[x] = 1, mx[x] = 0;
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (y == fa) continue;
        dfs1(y, x);
        if (sz[y] > (n >> 1)) ff = 0;
        sz[x] += sz[y];
        mx[x] = max(mx[x], sz[y]);
    }
    if ((n - sz[x]) > (n >> 1)) ff = 0;
    if (ff && !rt) rt = x;
}

void dfs2(int x, int fa) {
    add(C1, sz[fa], -1);
    add(C1, n - sz[x], 1);
    if (x ^ rt) {
        ans += 1ll * x * (ask(C1, n - 2 * mx[x]) - ask(C1, n - 2 * sz[x] - 1));
        ans += 1ll * x * (ask(C2, n - 2 * mx[x]) - ask(C2, n - 2 * sz[x] - 1));
        if (mark[fa]) mark[x] = 1;
        ans += rt * (sz[x] <= n - 2 * sz[mark[x] ? v : u]);  // rt 的贡献直接维护
    }
    add(C2, sz[x], 1);
    for (int i = 0; i < g[x].size(); i++) {
        int y = g[x][i];
        if (y == fa) continue;
        dfs2(y, x);
    }
    add(C1, sz[fa], 1);
    add(C1, n - sz[x], -1);
    if (x ^ rt) {
        ans -= 1ll * x * (ask(C2, n - 2 * mx[x]) - ask(C2, n - 2 * sz[x] - 1));
    }
}

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        rep(i, 1, n) g[i].clear();
        rep(i, 1, n - 1) {
            int x, y; scanf("%d%d", &x, &y);
            g[x].push_back(y), g[y].push_back(x);
        }
        ans = rt = 0;
        dfs1(1, 0);
        dfs1(rt, 0);
        u = v = 0;
        for (int i = 0; i < g[rt].size(); i++) {
            int x = g[rt][i];
            if (sz[x] > sz[u]) v = u, u = x;
            else if (sz[x] > sz[v]) v = x;
        }
        rep(i, 1, n + 1) C1[i] = C2[i] = 0, mark[i] = 0;
        rep(i, 1, n) add(C1, sz[i], 1);
        mark[u] = 1;
        dfs2(rt, 0);
        printf("%lld\n", ans);
    }
    return 0;
}